package com.zsj.stack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/3/24 14:48
 * @Description
 */
public class LeetCodeStackQuestion {

    public static void main(String[] args) {
        System.out.println(isValid2("({})"));
//        System.out.println(isValid2("))"));
//        System.out.println(isValid2("()[]{}"));
//        System.out.println(isValid2("(){}}{"));
//        System.out.println(evalRPN2(new String[]{"2", "1", "+", "3", "*"}));
//        System.out.println(evalRPN2(new String[]{"4", "13", "5", "/", "+"}));
//        String s = new LeetCodeStackQuestion().infixToSuffix("1+2*3*4-1");
//        System.out.println(s);//123*+4-
//        String[] strings = new String[s.length()];
//        char[] chars = s.toCharArray();
//        for (int i = 0; i < chars.length; i++) {
//            strings[i] = String.valueOf(chars[i]);
//        }
//        System.out.println(evalRPN(strings));
//        System.out.println(new LeetCodeStackQuestion().infixToSuffix2("(1+2)*3*4-1"));
    }


    Map<Character, Integer> dictionary = new HashMap<>();


    /**
     * 源码级别的分析
     * 在我们的平常写代码都是使用中缀的方法进行代码编写的
     * 而在java的编译底层实现 是将我们的中缀表达式 转换为后缀表达式
     * 在进行表达式求值的
     * 1 + 2 ===> 1 2 +
     * 1 + 2 * 3 - 4 ===> 123*+4-
     * 思路: 表达式由数字与运算符构成
     * 当遇到数字的时候将数字拼接到字符串上 遇到运算符将它压入栈中
     * 如果遇到同级运算符 将之前压入栈的运算符进行弹栈并且拼接到字符中
     * <p>
     * a + b * c ===> abc*+ <br/>
     * a * b + c ===> ab*c+
     */
    //中缀转后缀
    public String infixToSuffix(String exp) {
        dictionary.put('+', 1);
        dictionary.put('-', 1);
        dictionary.put('*', 2);
        dictionary.put('/', 2);
        if (exp.length() <= 1) return exp;
        char[] chars = exp.toCharArray();
        Stack<Character> stack = new LinkedStack<>(exp.length());
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if (dictionary.containsKey(chars[i])) {
                //说明拿到的是运算符
                if (!stack.isEmpty()) {
                    //不为空 对比级别 级别不一样就继续压栈
                    //否则我们弹栈
                    Integer level = dictionary.get(chars[i]);
                    Integer integer = dictionary.get(stack.peak());
                    if (level.equals(integer)) {
                        //说明级别一致 将栈中元素拿出来 在将刚读取的这个运算符压栈
                        stringBuilder.append(stack.pop());
                        stack.push(chars[i]);
                    } else if (level > integer) {
                        //说明当前读取的元素比栈中的等级要高 继续压入
                        stack.push(chars[i]);
                    } else {
                        //说明栈中元素比当前读取元素的等级要高
                        //将栈中元素弹出并且追加到字符中
                        stringBuilder.append(stack.pop());
                        stack.push(chars[i]);
                    }
                } else stack.push(chars[i]);

            } else {
                //说明拿到的是数字
                stringBuilder.append(chars[i]);
            }
        }
        if (!stack.isEmpty()) {
            //到这里说明字符遍历完成 栈中不为空 将栈中所有运算符追加到结果上
            while (!stack.isEmpty()) {
                stringBuilder.append(stack.pop());
            }
        }
        return stringBuilder.toString();
    }

    //中缀转后缀(带括号)
    public String infixToSuffix2(String exp) {
        dictionary.put('+', 1);
        dictionary.put('-', 1);
        dictionary.put('*', 2);
        dictionary.put('/', 2);
        if (exp.length() <= 1) return exp;
        char[] chars = exp.toCharArray();
        Stack<Character> stack = new LinkedStack<>(exp.length());
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                stack.push(chars[i]);
                continue;
            }
            if (dictionary.containsKey(chars[i])) {
                //运算符
                if (stack.isEmpty() || stack.peak().equals('(')) {
                    stack.push(chars[i]);
                } else if (dictionary.get(chars[i]) >= dictionary.get(stack.peak())) {
                    //相等 将与它相同的元素全部追加
                    stringBuilder.append(stack.pop()).append(chars[i]);
                } else if (dictionary.get(chars[i]) < dictionary.get(stack.peak())) {
                    //当前元素小于栈中元素
                    stringBuilder.append(stack.pop());
                    stack.push(chars[i]);
                } else stack.push(chars[i]);
            } else if (chars[i] == ')') {
                //右括号
                while (!stack.peak().equals('(')) {
                    stringBuilder.append(stack.pop());
                }
                stack.pop();//将左括号弹出
            } else {
                //数字
                stringBuilder.append(chars[i]);
            }
        }
        while (!stack.isEmpty()) stringBuilder.append(stack.pop());
        return stringBuilder.toString();
    }

    /**
     * LCR 036. 逆波兰表达式求值
     * 中缀表达式 1+2
     * 后缀表达式 1 2 +
     * <p>
     * 思路
     * 每次遇到数字都将其压入栈中  遇到运算符就将前两个数字弹出来进行运算后在进行压栈
     */
    public static int evalRPN(String[] tokens) {
        if (tokens.length == 0) return 0;
        List<String> s = new ArrayList<>();
        Stack<String> stack = new ArrayStack<>(tokens.length);
        s.add("+");
        s.add("-");
        s.add("*");
        s.add("/");
        for (int i = 0; i < tokens.length; i++) {
            if (s.contains(tokens[i])) {
                //说明遇到的是符号
                String pop = stack.pop();
                String pop1 = stack.pop();
                if (tokens[i].equals(s.get(0))) {
                    //加法 将压完的结果再次放入栈中
                    stack.push(String.valueOf
                            (Integer.parseInt(pop1) + Integer.parseInt(pop)));
                }
                if (tokens[i].equals(s.get(1))) {
                    //加法 将压完的结果再次放入栈中
                    stack.push(String.valueOf
                            (Integer.parseInt(pop1) - Integer.parseInt(pop)));
                }
                if (tokens[i].equals(s.get(2))) {
                    //加法 将压完的结果再次放入栈中
                    stack.push(String.valueOf
                            (Integer.parseInt(pop1) * Integer.parseInt(pop)));
                }
                if (tokens[i].equals(s.get(3))) {
                    //加法 将压完的结果再次放入栈中
                    stack.push(String.valueOf
                            (Integer.parseInt(pop1) / Integer.parseInt(pop)));
                }
            } else {
                //说明遇到的数字 数字就压栈就行
                stack.push(tokens[i]);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    public static int evalRPN2(String[] tokens) {
        if (tokens.length == 0) return 0;
        List<String> s = new ArrayList<>();
        java.util.Stack<String> stack = new java.util.Stack<>();
        s.add("+");
        s.add("-");
        s.add("*");
        s.add("/");
        for (int i = 0; i < tokens.length; i++) {
            if (s.contains(tokens[i])) {
                //说明遇到的是符号
                String pop = stack.pop();
                String pop1 = stack.pop();
                if (tokens[i].equals(s.get(0))) {
                    //加法 将压完的结果再次放入栈中
                    stack.push(String.valueOf
                            (Integer.parseInt(pop1) + Integer.parseInt(pop)));
                }
                if (tokens[i].equals(s.get(1))) {
                    //加法 将压完的结果再次放入栈中
                    stack.push(String.valueOf
                            (Integer.parseInt(pop1) - Integer.parseInt(pop)));
                }
                if (tokens[i].equals(s.get(2))) {
                    //加法 将压完的结果再次放入栈中
                    stack.push(String.valueOf
                            (Integer.parseInt(pop1) * Integer.parseInt(pop)));
                }
                if (tokens[i].equals(s.get(3))) {
                    //加法 将压完的结果再次放入栈中
                    stack.push(String.valueOf
                            (Integer.parseInt(pop1) / Integer.parseInt(pop)));
                }
            } else {
                //说明遇到的数字 数字就压栈就行
                stack.push(tokens[i]);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    /**
     * 20. 有效的括号
     * 相当于每次遍历左括号的时候记录它对应的括号并且记录到栈中
     * 如果遍历到右括号的时候则对应他与栈顶元素是否相同
     * 相同则继续且弹栈 否则就返回false
     */
    public static boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;//奇数肯定不对
        char[] chars = s.toCharArray();
        Stack<Character> stack = new ArrayStack<>(chars.length);
        Map<Character, Character> dic = new HashMap<>();
        dic.put('(', ')');
        dic.put('[', ']');
        dic.put('{', '}');
        for (int i = 0; i < chars.length; i++) {
            if (dic.containsKey(chars[i])) {
                stack.push(dic.get(chars[i]));
            } else {
                //说明拿到是右括号
                if (i == 0) return false;//第一个元素为右括号直接打死
                //我们上面每次添加的时候说明有个对应的左括号是被扫描到了的
                Character pop = stack.pop();
                if (pop == null) return false;//如果弹栈失败 说明栈为空 之前根本没有扫到左括号
                if (pop != chars[i]) return false;//如果弹出来的元素与对应元素不相同的话也打死
            }
        }
        return stack.isEmpty();
    }

    public static boolean isValid2(String s) {
        if (s.length() % 2 != 0) return false;//奇数肯定不对
        char[] chars = s.toCharArray();
        java.util.Stack<Character> stack = new java.util.Stack<>();
        Map<Character, Character> dic = new HashMap<>();
        dic.put('(', ')');
        dic.put('[', ']');
        dic.put('{', '}');
        for (int i = 0; i < chars.length; i++) {
            if (dic.containsKey(chars[i])) {
                //说明是左括号 将对应的所需括号压栈
                stack.push(dic.get(chars[i]));
            } else {
                //说明拿到是右括号
                if (i == 0) return false;//第一个元素为右括号直接打死
                //我们上面每次添加的时候说明有个对应的左括号是被扫描到了的
                if (stack.isEmpty()) return false;//如果弹栈失败 说明栈为空 之前根本没有扫到左括号
                Character pop = stack.pop();
                if (pop != chars[i]) return false;//如果弹出来的元素与对应元素不相同的话也打死
            }
        }
        return stack.isEmpty();
    }


}
